/* Copyright Paul Reiche, Fred Ford. 1992-2002, Christopher Night 2013

This file is part of the HTML5 port of Ur-Quan Masters (UQM-HTML5)

UQM-HTML5 is free software: you can redistribute it and/or modify it under the terms of the GNU
General Public License as published by the Free Software Foundation, either version 3 of the
License, or (at your option) any later version.

UQM-HTML5 is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
Public License for more details.

You should have received a copy of the GNU General Public License along with this program.  If not,
see <http://www.gnu.org/licenses/>. */


// Port/rewrite of src/uqm/collide.c and src/uqm/intersec.js

// This collision algorithm I went with is a bit of a compromise. The problem arises that, to be
//   physically realistic, certain collisions *should* introduce a torque. This is most noticeable
//   if you have wide bodies (eg, two Earthling Cruisers moving sideways) colliding with glancing
//   trajectories. But, since we can't induce rotation, we have to go with something unrealistic.
// I decided to go with applying an impulse in the same direction as you would have gotten if a
//   torque were also applied, but with an amount chosen to conserve energy.

var COLLISION_TURN_WAIT = 1
var COLLISION_THRUST_WAIT = 3

var collide = {
	// TODO: double check this logic because the macro is hard to read
	CollisionPossible: function (element0, element1) {
		var state0 = element0.state, state1 = element1.state
		if (state0.SKIP_COLLISION) return false
		if (state0.COLLISION && state1.COLLISION) return false
		if (state0.IGNORE_SIMILAR && state1.IGNORE_SIMILAR &&
			element0.parent === element1.parent)
			return false
		if (!element0.mass && !element1.mass) return false
		return true
	},

	// Given two drawable elements and the displacement they want to travel this frame
	// Return null if they never intersect
	// Return [t, fx0, fy0, fx1, fy1] as the last point at which they're not intersecting
	// t is a value between 0 and 1, a fraction of the frame
	// Assumes they begin not intersecting
	// This is a significant rewrite of the original function in intersec.c
	// Will not give the exact same results.
	DrawablesIntersect: function (element0, element1) {
		var pc0 = element0.current, pn0 = element0.next
		var pc1 = element1.current, pn1 = element1.next
		var dx0 = zmod(pn0.px-pc0.px, ARENA_WIDTH), dy0 = zmod(pn0.py-pc0.py, ARENA_HEIGHT)
		var dx1 = zmod(pn1.px-pc1.px, ARENA_WIDTH), dy1 = zmod(pn1.py-pc1.py, ARENA_HEIGHT)
		//console.log(pc0, pn0, pc1, pn1, dx0, dy0, dx1, dy1)
		// This function operates in rounded whole-pixel coordinates
		if (!dx0 && !dy0 && !dx1 && !dy1) return null
		var px0 = pc0.px, py0 = pc0.py, px1 = pc1.px, py1 = pc1.py
		px1 = px0 + zmod(px1 - px0, ARENA_WIDTH)
		py1 = py0 + zmod(py1 - py0, ARENA_HEIGHT)
		
		// Step 1: coarse detection. Return null if the bounding boxes never intersect

		// Get the upper-left corners of the frames
		var frame0 = element0.current.frame, frame1 = element1.current.frame
		var cx0 = px0 - frame0.hotspotx, cy0 = py0 - frame0.hotspoty
		var cx1 = px1 - frame1.hotspotx, cy1 = py1 - frame1.hotspoty
		var w0 = frame0.img.width, h0 = frame0.img.height
		var w1 = frame1.img.width, h1 = frame1.img.height
		
		// Distance from end of one box to start of next
		var tx0 = cx0 + w0 - cx1, ty0 = cy0 + h0 - cy1
		var tx1 = cx1 + w1 - cx0, ty1 = cy1 + h1 - cy0
		
		var Dx = dx0 - dx1, Dy = dy0 - dy1

		if (tx0 <= 0 && tx0 + Dx <= 0) return null  // element1 remains to the right of element0
		if (tx1 <= 0 && tx1 - Dx <= 0) return null  // element0 remains to the right of element1
		if (ty0 <= 0 && ty0 + Dy <= 0) return null  // element1 remains above element0
		if (ty1 <= 0 && ty1 - Dy <= 0) return null  // element0 remains above element1

		//console.log("ts", cx0, cx1, cy0, cy1, tx0, tx1, ty0, ty1, Dx, Dy)
		
		// Step 2: fine detection. Step each element ahead one pixel at a time until we find
		//   a collision
		
		var image0 = frame0.img, image1 = frame1.img
		var t = 0, mx0 = 0, my0 = 0, mx1 = 0, my1 = 0   // amount each element has moved so far
		var steps = this.steps(dx0, dy0, dx1, dy1)
		var r = [0, px0, py0, px1, py1]  // Last viable (non-colliding) point
		
		for (var j = 0 ; j < steps.length ; ++j) {
			var step = steps[j]
			t = step[0] ; mx0 += step[1] ; my0 += step[2] ; mx1 += step[3] ; my1 += step[4]
			if (this.overlap(image0, image1, cx1 + mx1 - cx0 - mx0, cy1 + my1 - cy0 - my0)) {
				return r
			}
			r = [t, px0 + mx0, py0 + my0, px1 + mx1, py1 + my1]
		}
		return null
		
	},

	// Given two images whose corners are relatively displaced by (dx, dy), is there any pixel where
	//  they overlap?
	overlap: function(image0, image1, dx, dy) {
		// Check whether the bounding boxes overlap
		var w0 = image0.width, h0 = image0.height
		var w1 = image1.width, h1 = image1.height
		//console.log("olap", dx, dy, w0, h0, w1, h1)
		if (dx >= w0 || dx <= -w1 || dy >= h0 || dy <= -h1) return false
		// TODO: pixel-perfect collision check goes here
		// Check each overlapping pixel. If both have alpha > 0 then collision occurs
		return true
	},

	
	// Return a series of one-pixel steps
	// For when we want to advance two objects one pixel at a time until they collide
	stepcache: {},
	steps: function (dx0, dy0, dx1, dy1) {
		var key = [dx0, dy0, dx1, dy1]
		if (key in this.stepcache) return this.stepcache[key]
		var r = []
		this.linesteps(dx0, dy0).forEach(function (s) { r.push([s[0], s[1], s[2], 0, 0]) })
		this.linesteps(dx1, dy1).forEach(function (s) { r.push([s[0], 0, 0, s[1], s[2]]) })
		// Lexicographically sort the elements. The first element is time
		// Beyond that the order doesn't matter but it needs to be consistent.
		// If JavaScript guaranteed a stable sort we could just sort on the first element
		r.sort(function (b, a) {
			return b[0]-a[0] || b[1]-a[1] || b[2]-a[2] || b[3]-a[3] || b[4]-a[4]
		})
		if (Math.abs(dx0) + Math.abs(dy0) + Math.abs(dx1) + Math.abs(dy1) < 20) {
			this.stepcache[key] = r
		}
		return r
	},
	
	// A series of one-pixel steps to draw a line (dx, dy)
	// using Breshenham's algorithm
	linestepcache: {},
	linesteps: function (dx, dy) {
		var key = [dx, dy]
		if (key in this.linestepcache) return this.linestepcache[key]
		var r = []
		if (dx < 0) {
			this.linesteps(-dx, dy).forEach(function (a) { r.push([a[0], -a[1], a[2]]) })
		} else if (dy < 0) {
			this.linesteps(dx, -dy).forEach(function (a) { r.push([a[0], a[1], -a[2]]) })
		} else if (dx < dy) {
			this.linesteps(dy, dx).forEach(function (a) { r.push([a[0], a[2], a[1]]) })
		} else {
			var e = Math.floor(dx / 2), y = 0
			for (var x = 1 ; x <= dx ; ++x) {
				e -= dy
				if (e < 0) {
					e += dx ; ++y 
					r.push([x / dx, 1, 1])
				} else {
					r.push([x / dx, 1, 0])
				}
			}
		}
		this.linestepcache[key] = r
		return r
	},


	approaching: function (element0, element1) {
		if (element0.state.ALWAYS_APPROACHING || element1.state.ALWAYS_APPROACHING) return true
		var dx_rel = zmod(element1.next.x - element0.next.x, ARENA_WIDTH)
		var dy_rel = zmod(element1.next.y - element0.next.y, ARENA_HEIGHT)
		var dvx_rel = element1.vx - element0.vx
		var dvy_rel = element1.vy - element0.vy
		return dvx_rel * dx_rel + dvy_rel * dy_rel <= 0
	},

	// Update the velocities and "next" positions of the two elements when they bounce off each
	//   other.
	collide: function (element0, element1) {
		var dx_rel = zmod(element1.next.x - element0.next.x, ARENA_WIDTH)
		var dy_rel = zmod(element1.next.y - element0.next.y, ARENA_HEIGHT)
		var dvx_rel = element1.vx - element0.vx
		var dvy_rel = element1.vy - element0.vy
		var Directness = dvx_rel * dx_rel + dvy_rel * dy_rel
		var disp2 = dx_rel * dx_rel + dy_rel * dy_rel
		//var speed = Math.sqrt(dvx_rel * dvx_rel + dvy_rel * dvy_rel)
		//var dvproj = Directness / disp
		
		var mass0 = element0.mass, mass1 = element1.mass
		// technically dp / disp
		var dp = 2 * Directness * mass0 * mass1 / ((mass0 + mass1) * disp2)
		var dpx = dx_rel * dp
		var dpy = dy_rel * dp
		if (Math.abs(dpx) + Math.abs(dpy) > 1000) throw "The delta-p is too damn high!"
		//var E0 = element0.vx * element0.vx + element0.vy * element0.vy + element1.vx * element1.vx + element1.vy * element1.vy
	    var dv0 = this.knock(element0, dpx, dpy)
	    var dv1 = this.knock(element1, -dpx, -dpy)
		//var E1 = element0.vx * element0.vx + element0.vy * element0.vy + element1.vx * element1.vx + element1.vy * element1.vy
	    //console.log(dx_rel, dy_rel, dvx_rel, dvy_rel, dp, dpx, dpy)
	    this.nudge(element0, dv0, element1, dv1)
	},
	
	// Change the momentum of the element as the result of a collision
	// (this is a new function to reduce code duplication)
	knock: function (element, dpx, dpy) {
		if (element.state.GRAVITY_MASS) return null
		if (element.state.PLAYER_SHIP) {
			element.status.SHIP_AT_MAX_SPEED = false
			element.status.SHIP_BEYOND_MAX_SPEED = false
			if (!element.state.DEFY_PHYSICS) {
				if (element.turn_wait < COLLISION_TURN_WAIT)
					element.turn_wait += COLLISION_TURN_WAIT
				if (element.thrust_wait < COLLISION_THRUST_WAIT)
					element.thrust_wait += COLLISION_THRUST_WAIT
			}
		}
		var dvx = dpx / element.mass
		var dvy = dpy / element.mass
		//console.log("knock", element.vx, element.vy, dvx, dvy)
		element.vx += dvx
		element.vy += dvy
		if (element.vx * element.vx + element.vy * element.vy < 1) {
			// There's some weird logic here when the velocity is less than 1 (in scaled units)
			// Technically when abs(vx) + abs(vy) < 1
			// TODO: check this out and figure out if it still applies, or if it's only needed
			// for fixed-point calculations
		}
		return [dvx, dvy]
	},
	
	// To be used after two elements have bounced off each other and updated their velocities.
	// Scootch them apart in the direction of the delta-v until they no longer overlap.
	// Handle the case when dv = null (the object is fixed, eg, a planet)
	nudge: function (element0, dv0, element1, dv1) {
		var v0 = dv0 ? Math.sqrt(dv0[0] * dv0[0] + dv0[1] * dv0[1]) : 0
		var v1 = dv1 ? Math.sqrt(dv1[0] * dv1[0] + dv1[1] * dv1[1]) : 0
		// TODO: handle this case but I don't really feel like it right now.
		if (!v0 && !v1) {
			console.log(element0, dv0, element1, dv1)
			throw "You are a PAIN, you know that?"
		}
		dv0 = dv0 || [0, 0]
		dv1 = dv1 || [0, 0]
		var dt = 0.5 / Math.max(v0, v1), t = 0
		var dx0, dy0, dx1, dy1, key = null
		var frame0 = element0.next.frame, frame1 = element1.next.frame
		var sx = element1.next.px - frame1.hotspotx - element0.next.px + frame0.hotspotx
		var sy = element1.next.py - frame1.hotspoty - element0.next.py + frame0.hotspoty
		var img0 = frame0.img, img1 = frame1.img
		// Step the objects apart in the direction they were knocked, one pixel at a time,
		//   and stop when they no longer overlap
		do {
			dx0 = Math.round(dv0[0] * t) ; dy0 = Math.round(dv0[0] * t)
			dx1 = Math.round(dv1[0] * t) ; dy1 = Math.round(dv1[0] * t)
			t += dt
			var newkey = [dx0,dy0,dx1,dy1].toString()
			if (newkey === key) continue
			key = newkey
		} while (this.overlap(img0, img1, sx + dx1 - dx0, sy + dy1 - dy0))
		element0.next.x = element0.next.px += dx0
		element0.next.y = element0.next.py += dy0
		element1.next.x = element1.next.px += dx1
		element1.next.y = element1.next.py += dy1
		//console.log("nudge", dv0, dv1, dx0, dy0, dx1, dy1)
	},

}

